#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10000000

void fast_sort(int *a, int left, int right);
int main(int argc, const char **argv) {
  srand(time(NULL));
  clock_t start, end;
  double cpu_time_used;

  start = clock(); // 记录开始时间

  int *buf;
  buf = malloc(sizeof(int) * N);
  for (int i = 0; i < N; i++)
    buf[i] = rand() % N;

  fast_sort(buf,0,N - 1);
  end = clock(); // 记录结束时间

  cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC; // 计算CPU时间
  printf("程序运行时间为 %f 秒\n", cpu_time_used);
  return 0;
}


void fast_sort(int *a, int left, int right)
{
	int i=left;
	int j=right;
	int key=a[i];
	if(left >= right)
		return ;
	while(i<j)
	{
		while(a[j]>=key && i<j)
			j--;
		a[i]=a[j]; // 把这个数据的值放到左边去
		while(a[i]<=key && i<j)
			i++;
		a[j]=a[i]; // 把这个数据的值放到右边去
	}
	a[i] = key; // 当i和j相遇，存放key的值

	fast_sort(a, left, i-1);
	fast_sort(a, i+1, right);

}


